package _interview150;

/**
 * 79. 单词搜索
 */
public class No79 {
    private char[][] board;
    private String word;
    private int m, n, len;
    private boolean[][] path;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        m = board.length;
        n = board[0].length;
        len = word.length();
        this.path = new boolean[m][n];
        boolean ans = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word.charAt(0) && dfs(i, j, 0)) return true;
            }
        }
        return false;
    }

    private boolean dfs(int i, int j, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || k == len || path[i][j]) return false;
        if (word.charAt(k) != board[i][j]) return false;
        path[i][j] = true;
        if (k == len - 1) return true;
        boolean ans = dfs(i, j - 1, k + 1) || dfs(i, j + 1, k + 1) || dfs(i - 1, j, k + 1) || dfs(i + 1, j, k + 1);
        path[i][j] = false;
        return ans;
    }
}
